package katas.dynamic;

public class LongestIncreasingSequence {

	public int findLongest(int[] a){
		int[] l = new int[a.length];
		int max = 1;
		for(int i=0; i<a.length; i++){
			int lmax = 1;
			for(int j=0; j<i; j++){
				if(a[i] > a[j] && (l[j]+1)>lmax)
					lmax = l[j] + 1;
			}
			l[i] = lmax;
			if(lmax > max)
				max = lmax;
		}
		return max;
	}
	
	public static void main(String[] args) {
		LongestIncreasingSequence lis = new LongestIncreasingSequence();
		System.out.println(lis.findLongest(new int[]{2,4,3,5,1,7,6,9,8}));
	}
}
